Defining the 'Minimum' Spanning Tree (MST)

Now that we understand what a spanning tree is, we can see that a single graph can have many different valid ones. But in a weighted graph where edges have costs, how do we decide which spanning tree is the 'best'?

The "best" tree is typically the one with the lowest total cost. We can find the cost of any spanning tree by summing the weights of all its edges.
This leads us to our core objective: finding the Minimum Spanning Tree (MST).
An MST is a spanning tree whose total edge weight is less than or equal to the weight of every other possible spanning tree for that graph.
It's important to note that a graph can have more than one MST if multiple spanning trees share the same, lowest possible total weight. The goal is to find *a* tree with that minimum weight, not necessarily a unique one.

Minimum Spanning Tree (MST)

For a given connected, undirected, and weighted graph $G = (V, E)$, a Minimum Spanning Tree (MST) is a spanning tree $T = (V, E')$ where $E' \subseteq E$ such that the total weight $\Sigma w(u, v)$ for all edges $(u, v) \in E'$ is minimized.